package leetcode.D500.T437;

import util.TreeNode;

import java.util.HashMap;
import java.util.Map;

class Solution {

    // 记录前缀和对应数量，key:前缀和, value:路径数量
    private static Map<Long, Integer> map = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L, 1);
        return getSum(root, targetSum, 0);
    }

    private int getSum(TreeNode root, int targetSum, long sum) {
        if (root == null)
            return 0;
        sum += root.val;
        int num = map.getOrDefault(sum - targetSum, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        num += getSum(root.left, targetSum, sum);
        num += getSum(root.right, targetSum, sum);
        map.put(sum, map.get(sum) - 1);    // 回溯的思想：消除对后续的影响
        return num;
    }
}